The boom in the Internet and the rise of new network technologies have focused attention on designing faster and more efficient data networks. A key component of the data network is the data server. Data servers are the engines that store and feed content to diverse clients over the network media. Data servers can take many forms, such as infestations, wireless gateways, web servers or specialized servers such as traffic or weather information servers. Increasingly, data servers employ a multiple-channel, point-to-point model.
For example, FIG. 1 illustrates a typical multiple-channel communication system of the prior art, which satisfies job requests in a point-to-point, or unicast, fashion. In a point-to-point system, each client's request for data is required to be individually satisfied, even if more than one client makes a job request for the same data item. In this regard, a point-to point system is different from a broadcast system, which is used to advantage by satisfying all of the pending job requests for a data item with a single broadcast of the data item. One of many examples of a point-to-point system is a centralized Internet server which provides web page data in response to requests from different Internet users.
In FIG. 1, devices 30a through 30w make requests for data which are delivered to central server 10 via link 36, or by any other method. Specifically, device 30a makes a job request for data item a, device 30b makes a job request for data item b, and device 30w makes a job request for data item w. Central server 10 receives the job requests and retrieves the requested data from either an internal database or an external database (as will be shown below). Central server 10 stores the job requests in queue 12 and then transmits the requested data to one of a plurality of local channel servers, designated as 40-1 through 40-k. Each local channel server provides data to a corresponding data channel designated C1 through Ck. When requested data is received by one of the local channel servers, the local channel server then services the job by transmitting the requested data to the requesting device via its corresponding channel. Channel servers may employ signal processors that modulate the data to appropriate channels, such as in many proposed wireless base stations.
Additionally, a scheduling arrangement is employed by the system. The scheduling arrangement determines the order in which the job requests are serviced. In the prior art, one method which is typically employed for this purpose is a centralized scheduling method. According to a centralized scheduling method, the central server has a corresponding queue, such as queue 12 shown in FIG. 1. When a job request is received by the central server, the central server stores the data in its corresponding queue along with other pending job requests which have not yet been serviced. Local channel servers service the job requests which are sent to them by the central server. When a local channel server completes a job requests, it sends a signal to the central server. The signal instructs the central server to send the next pending job request for transmission via the local channel server's corresponding channel.
According to a centralized scheduling scheme, the central server employs a scheduling algorithm in order to determine which of the jobs pending in its corresponding queue are to be sent to a local channel server so as to be serviced first. One scheduling algorithm which is typically employed by a central server in a communication system employing a centralized scheduling method is a “round-robin” arrangement. Basically, the central server assigns data relating to a job request to the next available local channel server based on a first-in first-out scheme. However, this arrangement may be unsatisfactory, specifically with widely heterogeneous data requests (heterogeneous job requests are job requests having varying sizes).
Another scheduling algorithm employed by data servers is known as the “Shortest Remaining Processing Time” (hereinafter referred to as “SRPT”) algorithm. The SRPT algorithm produces a schedule which minimizes the time it takes to process all of the uncompleted jobs in a queue. The SRPT algorithm is typically employed when jobs arrive in a continuous stream, and is based upon a sum-flow metric. The relevant parameter of the sum-flow metric is the time a job spends in the system. The SRPT algorithm employs the sum-flow metric by summing the time that all jobs spend in the system, and schedules the pending jobs so as to minimize this summed amount of time.
However, the SRPT algorithm has the drawback that it leads to starvation. Starvation occurs when some job request to the server is delayed to an unbounded extent. For instance, starvation may occur when the servicing of a pending job request is continually delayed because the SRPT algorithm determines that incoming job requests are serviced prior to the pending job request. Although the SRPT algorithm can be desirable in some circumstances, the fact that specific job requests are delayed to an unbounded extent is unfair to the person who made the request which is delayed. Furthermore, the fact that some job requests are delayed to an unbounded extent prevents the owner of the server system from being able to make a quality-of-service guarantee to each user that the schedule will be responsive to each job and avoid starvation of any job.
Although the above-referenced scheduling methods have attempted to address data server performance issues, there is an ever increasing need for improved scheduling methods that provide satisfactory performance. Therefore, there exists a need for a system and method for optimally scheduling the transmission of data items in multiple-channel, point-to-point communication system.